Public Class Funciones
    Public Shared Function Validar(ByVal matriz As Array) As Boolean
        'Esta funcion servira para verificar que todas las ciudades sean alcanzables desde cualquier origen.
        'Se hara una busqueda "primero en profundidad" partiendo de la ciudad "0" que finalizara cuando se 
        'hayan visitado todas las ciudades una vez, o cuando no se pueda continuar
        Try
            Dim destinos As New ArrayList() 'Contendra la lista de ciudades. Las visitadas se iran eliminando de aqui
            Dim lista As New ArrayList() 'Contiene la lista que nodos que vamos visitando
            For i As Integer = 1 To matriz.GetUpperBound(0)
                destinos.Add(i)
            Next

            Dim origen As Integer
            lista.Add(0) 'La busqueda arranca por la ciudad 0

            While (lista.Count > 0)
                origen = lista(lista.Count - 1) 'El ultimo objeto de la lista es desde donde debemos seguir buscando
                For i As Integer = 0 To matriz.GetUpperBound(0)
                    If matriz(origen, i, 0) <> 0 Then 'Se verifica que exista un camino
                        If destinos.Contains(i) Then 'Se verifica que la ciudad a recorrer no haya sido ya recorrida
                            destinos.Remove(i)
                            If destinos.Count = 0 Then 'Aqui se determina si ya se han recorrido todas las ciudades
                                Return True 'Aqui se devuelve verdadero si se corta la busqueda
                            End If
                            lista.Add(i)
                            Exit For
                        End If
                    End If
                Next

                If origen = lista(lista.Count - 1) Then 'Si son iguales, quiere decir que no se puede buscar mas desde este nodo
                    lista.RemoveAt(lista.Count - 1) 'Subimos un nivel en el arbol para seguir por otro camino
                End If
            End While
            'Si el algoritmo llega a este punto significa que no se pudieron recorrer todas las ciudades
            'dado que sino, habria terminado antes. Por ello, aqui simplemente se devuelve el valor Falso
            Return False
        Catch
            Return False
        End Try
    End Function
End Class
